本系列目前是閱讀Parallel Programming in C with MPI and OpenMP一書的筆記與所見所聞！

延續之前幾篇

今天來分析

Butterfly Network

(圖片出處：課本投影片)

這個網路架構蠻特別的

使用方法要把processor處理器編號換算成二進位來看！

0 ~ 7 的二進位表示法依序是 000, 001, 010, 011, 100, 101, 110, 111

以目標為準，遇到 0 就往左走，遇到 1 就往右走！

例如：要從 0 走到 1 換算成二進位就是從0出發目標要走到 001

走的路徑為 左 左 右 : (0,0) -> (1,0), (1,0) -> (2,0), (2,0) -> (3,1)

走完後發現我們成功來到了 1 所在的那條線上的switch上面！

再舉一個例子：

例如：要從 2 走到 5 目標就是走到 101 --> 右左右

從(0,2)出發 -> 先向右來到 (1,6),

再從(1,6) -> 向左走到 (2,4)

從 (2,4) -> 向右走到 (3,5) 即成功到達 5 號處理器所在的那條線上的switch上！

觀察上面的網路線連接得知，每往下增加一層rank，彼此相連接的點縮減成一半！

這個網路拓樸的運作原理是用Radix sorting !

0,1,2,3 第一個bit是0

4,5,6,7 第一個bit是1

0,1 第二個bit是0

2,3 第二個bit是1

分析：

處理器數量設為 n

連完所有需要的switch連線後，rank的深度為 d

則我們得到 n = 2^d

上圖例有 8個processor (八個正方形)n=8, rank最大到3 所以d=3, 8 = 2^3

1. 這張圖 switch 數量 > processor數量 所以是Indirect Topology

2. Diameter: log n 這張圖的走訪法跟二元樹的search有異曲同工之妙！也就是每次往下走一層，就能過濾掉篩選一半的可能連線，越來越接近目標！

使用於上圖例就是 log 8 = 3 條，走3次即可到達目標！

3. Bisection width: n 這是個平均的近似值，可理解為傷上圖3號 跟 4號中間切斷，會需要切斷跟好8條線 (此圖n=8)，

但是也有許多種少於八條線跟多餘八條線的切法，所以如果把全部情況都討論完後取平均值會趨近 8 條！

4. Edges per node: 4 每一個switch都會被兩個上一層的連到，並且自己連出兩條線到下一層

5. Constant edge length? No 明顯可看出，有些線比較長，有些比較短

接著來介紹改良版本的butterfly network：

omaga network !!!

(圖片出處)

用法跟butterfly network相似

以目標號碼為準，遇到0就往上走，遇到1就往下走

例如：從 001走到 001 依序是 上 上 下，走的路徑為 A2 -往上-> B3 -往上-> C1 -往下-> 001 到達！

例如：從101走到 010 依序是 上 下 上，走的路徑為 A2 -往上-> B3 -往下-> C2 -往上-> 010 到達！

這個網路架構的優點

switch的數量隨著node數量變成兩倍，而多出一排！擴充性高！

例如：

這裡有8個處理器，則需要 4個 * 3排 switch

Diameter : log(n) 如圖的diameter都是 log(8) = 3

Bisection width : n 如圖可看出中間有三層(d=3) , 所以 2^d = 2^3 = 8

比起butterfly network這個網路有固定的Bisection width，不會有比較脆弱易切斷的地方，而且擴充性高！

現今常用于電話網路架構上！

(下回待續)